#define ElemType int

typedef struct ListNode List_Node;

void sortColors(int* nums, int numsSize);

#include "common.h"

int main()
{
	return 0;
}

void swap(int* nums, int x, int y)
{
	int t = nums[x];
	nums[x] = nums[y], nums[y] = t;
}

void sortColors(int* nums, int numsSize)
{
	// [0, eq_ptr) [eq_ptr, gt_ptr) [gt_ptr, numsSize)
	int eq_ptr = 0, gt_ptr = numsSize;
	for (int ptr = 0; ptr < gt_ptr;) 
		switch (nums[ptr]) {
			case 0: swap(nums, eq_ptr++, ptr++); break;
			case 1: ptr++; break;
			case 2: swap(nums, --gt_ptr, ptr); break;
		}
}
